home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / internet / other / ka9q / ka9q_src.arc / IPROUTE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-07-28  |  14.4 KB  |  597 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "internet.h"
  7. #include "timer.h"
  8. #include "netuser.h"
  9. #include "ip.h"
  10. #include "icmp.h"
  11. #include "iface.h"
  12. #include "trace.h"
  13.  
  14. struct route *routes[32][NROUTE];    /* Routing table */
  15. struct route r_default;            /* Default route entry */
  16.  
  17. int32 ip_addr;
  18. struct ip_stats ip_stats;
  19.  
  20. #ifndef    GWONLY
  21. struct mbuf *loopq;    /* Queue for loopback packets */
  22. #endif
  23.  
  24. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  25.  * coming or going, must pass.
  26.  *
  27.  * This router is a temporary hack, since it only does host-specific or
  28.  * default routing (no hierarchical routing yet).
  29.  *
  30.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  31.  * broadcast. The router will kick the packet upstairs regardless of the
  32.  * IP destination address.
  33.  */
  34. void
  35. ip_route(bp,rxbroadcast)
  36. struct mbuf *bp;
  37. char rxbroadcast;    /* True if packet had link broadcast address */
  38. {
  39.     struct mbuf *htonip();
  40.     struct ip ip;            /* IP header being processed */
  41.     int16 ip_len;            /* IP header length */
  42.     int16 length;            /* Length of data portion */
  43.     int32 gateway;            /* Gateway IP address */
  44.     register struct route *rp;    /* Route table entry */
  45.     struct route *rt_lookup();
  46.     int16 offset;            /* Offset into current fragment */
  47.     int strict = 0;            /* Strict source routing flag */
  48.     char precedence;        /* Extracted from tos field */
  49.     char delay;
  50.     char throughput;
  51.     char reliability;
  52.     int16 opt_len;    /* Length of current option */
  53.     char *opt;    /* -> beginning of current option */
  54.     char *ptr;    /* -> pointer field in source route fields */
  55.     struct mbuf *tbp;
  56.  
  57.     ip_stats.total++;
  58.     if(len_mbuf(bp) < IPLEN){
  59.         /* The packet is shorter than a legal IP header */
  60.         ip_stats.runt++;
  61.         free_p(bp);
  62.         return;
  63.     }
  64.     /* Sneak a peek at the IP header's IHL field to find its length */
  65.     ip_len = (bp->data[0] & 0xf) << 2;
  66.     if(ip_len < IPLEN){
  67.         /* The IP header length field is too small */
  68.         ip_stats.length++;
  69.         free_p(bp);
  70.         return;
  71.     }
  72.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  73.         /* Bad IP header checksum; discard */
  74.         ip_stats.checksum++;
  75.         free_p(bp);
  76.         return;
  77.     }
  78.     /* Extract IP header */
  79.     ntohip(&ip,&bp);
  80.  
  81.     if(ip.version != IPVERSION){
  82.         /* We can't handle this version of IP */
  83.         ip_stats.version++;
  84.         free_p(bp);
  85.         return;
  86.     }
  87.     /* Trim data segment if necessary. */
  88.     length = ip.length - ip_len;    /* Length of data portion */
  89.     trim_mbuf(&bp,length);    
  90.                 
  91.     /* Process options, if any. Also compute length of secondary IP
  92.      * header in case fragmentation is needed later
  93.      */
  94.     strict = 0;
  95.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  96.         int32 get32();
  97.  
  98.         /* Most options have a length field. If this is a EOL or NOOP,
  99.          * this (garbage) value won't be used
  100.          */
  101.         opt_len = opt[1] & 0xff;
  102.  
  103.         switch(opt[0] & OPT_NUMBER){
  104.         case IP_EOL:
  105.             goto no_opt;    /* End of options list, we're done */
  106.         case IP_NOOP:
  107.             opt_len = 1;
  108.             break;        /* No operation, skip to next option */
  109.         case IP_SSROUTE:    /* Strict source route & record route */
  110.             strict = 1;    /* note fall-thru */
  111.         case IP_LSROUTE:    /* Loose source route & record route */
  112.             /* Source routes are ignored unless we're in the
  113.              * destination field
  114.              */
  115.             if(ip.dest != ip_addr)
  116.                 break;    /* Skip to next option */
  117.             if((opt[2] & 0xff) >= opt_len){
  118.                 break;    /* Route exhausted; it's for us */
  119.             }
  120.             /* Put address for next hop into destination field,
  121.              * put our address into the route field, and bump
  122.              * the pointer
  123.              */
  124.             ptr = opt + (opt[2] & 0xff) - 1;
  125.             ip.dest = get32(ptr);
  126.             put32(ptr,ip_addr);
  127.             opt[2] += 4;
  128.             break;
  129.         case IP_RROUTE:    /* Record route */
  130.             if((opt[2] & 0xff) >= opt_len){
  131.                 /* Route area exhausted; kick back an error */
  132.                 union icmp_args icmp_args;
  133.  
  134.                 icmp_args.pointer = IPLEN + opt - ip.options;
  135.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  136.                 free_p(bp);
  137.                 return;
  138.             }
  139.             /* Add our address to the route */
  140.             ptr = opt + (opt[2] & 0xff) - 1;
  141.             ptr = put32(ptr,ip_addr);
  142.             opt[2] += 4;
  143.             break;
  144.         }
  145.     }
  146. no_opt:
  147.  
  148.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  149.     if(ip.dest == ip_addr || rxbroadcast){
  150. #ifdef    GWONLY
  151.     /* We're only a gateway, we have no host level protocols */
  152.         if(!rxbroadcast)
  153.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  154.         free_p(bp);
  155. #else
  156.         /* Put IP header back on */
  157.         if((bp = htonip(&ip,bp)) == NULLBUF)
  158.             return;
  159.  
  160.         /* If this is a local loopback packet, place on the loopback
  161.          * queue for processing in the main loop. This prevents the
  162.          * infinite stack recursion and other problems that would
  163.          * otherwise occur when we talk to ourselves, e.g., with ftp
  164.          */
  165.         if(ip.source == ip_addr){
  166.             /* LOOPBACK TRACING GOES HERE */
  167.             /* Copy loopback packet into new buffer.
  168.              * This avoids an obscure problem with TCP which
  169.              * dups its outgoing data before transmission and
  170.              * then frees it when an ack comes, even though the
  171.              * receiver might not have actually read it yet
  172.              */
  173.             tbp = copy_p(bp,len_mbuf(bp));
  174.             free_p(bp);
  175.             if(tbp != NULLBUF)
  176.                 enqueue(&loopq,tbp);
  177.         } else {
  178.             ip_recv(bp,rxbroadcast);
  179.         }
  180. #endif
  181.         return;
  182.     }
  183.  
  184.     /* Decrement TTL and discard if zero */
  185.     if(--ip.ttl == 0){
  186.         /* Send ICMP "Time Exceeded" message */
  187.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  188.         free_p(bp);
  189.         return;
  190.     }
  191.     /* Look up target address in routing table */
  192.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  193.         /* No route exists, return unreachable message */
  194.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  195.         free_p(bp);
  196.         return;
  197.     }
  198.     /* Find gateway; zero gateway in routing table means "send direct" */
  199.     if(rp->gateway == (int32)0)
  200.         gateway = ip.dest;
  201.     else
  202.         gateway = rp->gateway;
  203.  
  204.     if(strict && gateway != ip.dest){
  205.         /* Strict source routing requires a direct entry */
  206.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  207.         free_p(bp);
  208.         return;
  209.     }
  210.     precedence = PREC(ip.tos);
  211.     delay = ip.tos & DELAY;
  212.     throughput = ip.tos & THRUPUT;
  213.     reliability = ip.tos & RELIABILITY;
  214.  
  215.     if(ip.length <= rp->interface->mtu){
  216.         /* Datagram smaller than interface MTU; put header
  217.          * back on and send normally
  218.          */
  219.         bp = htonip(&ip,bp);
  220.         (*rp->interface->send)(bp,rp->interface,gateway,
  221.             precedence,delay,throughput,reliability);
  222.         return;
  223.     }
  224.     /* Fragmentation needed */
  225.     if(ip.fl_offs & DF){
  226.         /* Don't Fragment set; return ICMP message and drop */
  227.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  228.         free_p(bp);
  229.         return;
  230.     }
  231.     /* Create fragments */
  232.     offset = (ip.fl_offs & F_OFFSET) << 3;
  233.     while(length != 0){        /* As long as there's data left */
  234.         int16 fragsize;        /* Size of this fragment's data */
  235.         struct mbuf *f_data;    /* Data portion of fragment */
  236.  
  237.         /* After the first fragment, should remove those
  238.          * options that aren't supposed to be copied on fragmentation
  239.          */
  240.         ip.fl_offs = offset >> 3;
  241.         if(length + ip_len <= rp->interface->mtu){
  242.             /* Last fragment; send all that remains */
  243.             fragsize = length;
  244.         } else {
  245.             /* More to come, so send multiple of 8 bytes */
  246.             fragsize = (rp->interface->mtu - ip_len) & 0xfff8;
  247.             ip.fl_offs |= MF;
  248.         }
  249.         ip.length = fragsize + ip_len;
  250.  
  251.         /* Move the data fragment into a new, separate mbuf */
  252.         if((f_data = alloc_mbuf(fragsize)) == NULLBUF){
  253.             free_p(bp);
  254.             break;
  255.         }
  256.         f_data->cnt = pullup(&bp,f_data->data,fragsize);
  257.  
  258.         /* Put IP header back on */
  259.         if((f_data = htonip(&ip,f_data)) == NULLBUF){
  260.             free_p(bp);
  261.             break;
  262.         }
  263.         /* and ship it out */
  264.         (*rp->interface->send)(f_data,rp->interface,gateway,
  265.             precedence,delay,throughput,reliability);
  266.  
  267.         offset += fragsize;
  268.         length -= fragsize;
  269.     }
  270. }
  271.  
  272. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  273. int
  274. rt_add(target,bits,gateway,metric,interface)
  275. int32 target;    /* Target IP address prefix */
  276. unsigned bits;    /* Size of target address prefix in bits (0-32) */
  277. int32 gateway;
  278. int metric;
  279. struct interface *interface;
  280. {
  281.     struct route *rp,**hp,*rt_lookup();
  282.     int16 hash_ip(),i;
  283.  
  284.     if(interface == NULLIF)
  285.         return -1;
  286.  
  287.     /* Zero bits refers to the default route */
  288.     if(bits == 0){
  289.         rp = &r_default;
  290.     } else {
  291.         if(bits > 32)
  292.             bits = 32;
  293.  
  294.         /* Mask off don't-care bits */
  295.         for(i=31;i >= bits;i--)
  296. #if (ATARI_ST && LATTICE)
  297.             target &=  (0x80000000 >> (i-1));    /* DG2KK */
  298. #else
  299.             target &= ~(0x80000000 >> i);
  300. #endif
  301.  
  302.         /* Search appropriate chain for existing entry */
  303.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  304.             if(rp->target == target)
  305.                 break;
  306.         }
  307.     }
  308.     if(rp == NULLROUTE){
  309.         /* The target is not already in the table, so create a new
  310.          * entry and put it in.
  311.          */
  312.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  313.             return -1;    /* No space */
  314.         /* Insert at head of table */
  315.         rp->prev = NULLROUTE;
  316.         hp = &routes[bits-1][hash_ip(target)];
  317.         rp->next = *hp;
  318.         if(rp->next != NULLROUTE)
  319.             rp->next->prev = rp;
  320.         *hp = rp;
  321.     }
  322.     rp->target = target;
  323.     rp->gateway = gateway;
  324.     rp->metric = metric;
  325.     rp->interface = interface;
  326.     return 0;
  327. }
  328.  
  329. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  330.  * if entry was not in table.
  331.  */
  332. int
  333. rt_drop(target,bits)
  334. int32 target;
  335. unsigned bits;
  336. {
  337.     register struct route *rp;
  338.     struct route *rt_lookup();
  339.     unsigned i;
  340.     int16 hash_ip();
  341.  
  342.     if(bits == 0){
  343.         /* Nail the default entry */
  344.         r_default.interface = NULLIF;
  345.         return 0;
  346.     }
  347.     if(bits > 32)
  348.         bits = 32;
  349.  
  350.     /* Mask off don't-care bits */
  351.     for(i=31;i > bits;i--)
  352. #if (ATARI_ST && LATTICE)
  353.         target &=  (0x80000000 >> (i-1));    /* DG2KK */
  354. #else
  355.         target &= ~(0x80000000 >> i);
  356. #endif
  357.  
  358.     /* Search appropriate chain for existing entry */
  359.     for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  360.         if(rp->target == target)
  361.             break;
  362.     }
  363.     if(rp == NULLROUTE)
  364.         return -1;    /* Not in table */
  365.  
  366.     if(rp->next != NULLROUTE)
  367.         rp->next->prev = rp->prev;
  368.     if(rp->prev != NULLROUTE)
  369.         rp->prev->next = rp->next;
  370.     else
  371.         routes[bits-1][hash_ip(target)] = rp->next;
  372.  
  373.     free((char *)rp);
  374.     return 0;
  375. }
  376.  
  377. /* Compute hash function on IP address */
  378. static int16
  379. hash_ip(addr)
  380. register int32 addr;
  381. {
  382.     register int16 ret;
  383.  
  384.     ret = hiword(addr);
  385.     ret ^= loword(addr);
  386.     ret %= NROUTE;
  387.     return ret;
  388. }
  389. #ifndef    GWONLY
  390. /* Given an IP address, return the MTU of the local interface used to
  391.  * reach that destination. This is used by TCP to avoid local fragmentation
  392.  */
  393. int16
  394. ip_mtu(addr)
  395. int32 addr;
  396. {
  397.     register struct route *rp;
  398.     struct route *rt_lookup();
  399.  
  400.     rp = rt_lookup(addr);
  401.     if(rp != NULLROUTE && rp->interface != NULLIF)
  402.         return rp->interface->mtu;
  403.     else
  404.         return 0;
  405. }
  406. #endif
  407. /* Look up target in hash table, matching the entry having the largest number
  408.  * of leading bits in common. Return default route if not found;
  409.  * if default route not set, return NULLROUTE
  410.  */
  411. static struct route *
  412. rt_lookup(target)
  413. int32 target;
  414. {
  415.     register struct route *rp;
  416.     int16 hash_ip();
  417.     unsigned bits;
  418.  
  419.     for(bits = 32;bits != 0; bits--){
  420.         if(bits != 32)
  421. #if (ATARI_ST && LATTICE)
  422.             target &=  (0x80000000 >> (bits-1));    /* DG2KK */
  423. #else
  424.             target &= ~(0x80000000 >> bits);
  425. #endif
  426.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  427.             if(rp->target == target)
  428.                 return rp;
  429.         }
  430.     }
  431.     if(r_default.interface != NULLIF)
  432.         return &r_default;
  433.     else
  434.         return NULLROUTE;
  435. }
  436. /* Convert IP header in host format to network mbuf */
  437. struct mbuf *
  438. htonip(ip,data)
  439. struct ip *ip;
  440. struct mbuf *data;
  441. {
  442.     int16 hdr_len;
  443.     struct mbuf *bp;
  444.     register char *cp;
  445.     int16 checksum;
  446.  
  447.     hdr_len = IPLEN + ip->optlen;
  448.     if((bp = alloc_mbuf(hdr_len)) == NULLBUF){
  449.         return NULLBUF;
  450.     }
  451.     bp->cnt = hdr_len;
  452.     cp = bp->data;
  453.     
  454.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  455.     *cp++ = ip->tos;
  456.     cp = put16(cp,ip->length);
  457.     cp = put16(cp,ip->id);
  458.     cp = put16(cp,ip->fl_offs);
  459.     *cp++ = ip->ttl;
  460.     *cp++ = ip->protocol;
  461.     cp = put16(cp,0);    /* Clear checksum */
  462.     cp = put32(cp,ip->source);
  463.     cp = put32(cp,ip->dest);
  464.     if(ip->optlen != 0)
  465.         memcpy(cp,ip->options,ip->optlen);
  466.  
  467.     /* Compute checksum and insert into header */
  468.     checksum = cksum(NULLHEADER,bp,hdr_len);
  469.     put16(&bp->data[10],checksum);
  470.  
  471.     bp->next = data;
  472.     return bp;
  473. }
  474. /* Extract an IP header from mbuf */
  475. ntohip(ip,bpp)
  476. struct ip *ip;
  477. struct mbuf **bpp;
  478. {
  479.     char v_ihl;
  480.     int16 ihl;
  481.  
  482.     v_ihl = pullchar(bpp);
  483.     ip->version = (v_ihl >> 4) & 0xf;
  484.     ip->tos = pullchar(bpp);
  485.     ip->length = pull16(bpp);
  486.     ip->id = pull16(bpp);
  487.     ip->fl_offs = pull16(bpp);
  488.     ip->ttl = pullchar(bpp);
  489.     ip->protocol = pullchar(bpp);
  490.     (void)pull16(bpp);    /* Toss checksum */
  491.     ip->source = pull32(bpp);
  492.     ip->dest = pull32(bpp);
  493.  
  494.     ihl = (v_ihl & 0xf) << 2;
  495.     if(ihl < IPLEN){
  496.         /* Bogus packet; header is too short */
  497.         return -1;
  498.     }
  499.     ip->optlen = ihl - IPLEN;
  500.     if(ip->optlen != 0)
  501.         pullup(bpp,ip->options,ip->optlen);
  502.  
  503.     return ip->optlen + IPLEN;
  504. }
  505. /* Perform end-around-carry adjustment */
  506. int16
  507. eac(sum)
  508. register int32 sum;    /* Carries in high order 16 bits */
  509. {
  510.     register int16 csum;
  511.  
  512.     while((csum = sum >> 16) != 0)
  513.         sum = csum + (sum & 0xffffL);
  514.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  515. }
  516. /* Checksum a mbuf chain, with optional pseudo-header */
  517. int16
  518. cksum(ph,m,len)
  519. struct pseudo_header *ph;
  520. register struct mbuf *m;
  521. int16 len;
  522. {
  523.     register unsigned int cnt, total;
  524.     register int32 sum, csum;
  525.     register unsigned char *up;
  526.     int16 csum1;
  527.     int swap = 0;
  528.     int16 lcsum();
  529.  
  530.     sum = 0l;
  531.  
  532.     /* Sum pseudo-header, if present */
  533.     if(ph != NULLHEADER){
  534.         sum = hiword(ph->source);
  535.         sum += loword(ph->source);
  536.         sum += hiword(ph->dest);
  537.         sum += loword(ph->dest);
  538.         sum += ph->protocol & 0xff;
  539.         sum += ph->length;
  540.     }
  541.     /* Now do each mbuf on the chain */
  542.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  543.         cnt = min(m->cnt, len - total);
  544.         up = (unsigned char *)m->data;
  545.         csum = 0;
  546.  
  547.         if(((long)up) & 1){
  548.             /* Handle odd leading byte */
  549.             if(swap)
  550.                 csum = *up++ & 0xff;
  551.             else
  552.                 csum = (int16)((*up++ & 0xff) << 8);
  553.             cnt--;
  554.             swap = !swap;
  555.         }
  556.         if(cnt > 1){
  557.             /* Have the primitive checksumming routine do most of
  558.              * the work. At this point, up is guaranteed to be on
  559.              * a short boundary
  560.              */
  561.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  562.             if(swap)
  563.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  564.             csum += csum1;
  565.         }
  566.         /* Handle odd trailing byte */
  567.         if(cnt & 1){
  568.             if(swap)
  569.                 csum += up[--cnt] & 0xff;
  570.             else
  571.                 csum += (int16)((up[--cnt] & 0xff) << 8);
  572.             swap = !swap;
  573.         }
  574.         sum += csum;
  575.         total += m->cnt;
  576.     }
  577.     /* Do final end-around carry, complement and return */
  578.     return ~eac(sum) & 0xffff;
  579. }
  580. /* Machine-independent, alignment insensitive network-to-host long conversion */
  581. static int32
  582. get32(cp)
  583. register char *cp;
  584. {
  585.     int32 rval;
  586.  
  587.     rval = *cp++ & 0xff;
  588.     rval <<= 8;
  589.     rval |= *cp++ & 0xff;
  590.     rval <<= 8;
  591.     rval |= *cp++ & 0xff;
  592.     rval <<= 8;
  593.     rval |= *cp & 0xff;
  594.  
  595.     return rval;
  596. }
  597.